/*
 * Copyright (c) 2021.版权所有高金磊
 */

package 领扣算法.AA中等题.摆动排序II;

import com.kenai.jffi.MemoryIO;
//import jdk.nashorn.internal.runtime.regexp.joni.constants.Traverse;
import orther.线程测试.Th;
import 领扣算法.A简单题.最小栈.MinStack;

import java.beans.Transient;
import java.util.Arrays;
import java.util.Date;
import java.util.LinkedList;
import java.util.logging.Level;

public class Main {

//    public void wiggleSort(int[] nums) {
//        Arrays.sort(nums);
//        LinkedList<Integer> data=new LinkedList<>();
//        for (int num : nums) {
//            data.addLast(num);
//        }
//        LinkedList<Integer> data_min=new LinkedList<>();
//        while (data.size()>data_min.size()){
//            data_min.addLast(data.pollFirst());
//        }
//        for (int i = 0; i < nums.length; i++) {
//
//            nums[i++]=data_min.pollFirst();
//            if (!data.isEmpty())
//                nums[i]=data.pollFirst();
//        }
//    }

    //桶排序
    Node node=new Node();
    LinkedList<Integer> res=new LinkedList<>();
    public void wiggleSort(int[] nums) {

        node.num=nums[0];
        for (int i = 1; i < nums.length; i++) {
            plus(nums[i]);
        }
        //中序遍历拿到排序答案
        Traverse(node);
        for (int i = 0; i < nums.length; i++) {
            nums[i]=res.pollFirst();
        }

    }
    private void plus(int num){
        Node middle=node;
        while (true){
            if (num<middle.num){
                if (middle.le_next==null){
                    middle.le_next=new Node();
                    middle.le_next.num=num;
                    return;
                }else {
                    middle=middle.le_next;
                }
            }else {
                if (middle.ri_next==null){
                    middle.ri_next=new Node();
                    middle.ri_next.num=num;
                    return;
                }else{
                    middle=middle.ri_next;
                }
            }
        }
    }
    private void Traverse(Node node){
       if (node==null){
           return;
       }
       Traverse(node.le_next);
        res.addLast(node.num);
        Traverse(node.ri_next);
    }
    public static void main(String arg[]){//main--来自高金磊
    
        new Main().wiggleSort(new int[]{1,1,2,1,2,2,1});
    }

}

class Node{
   public Node le_next;
   public Node ri_next;
   public int num;
}
